1. Field Of The Invention
This invention relates to digital systems, and more particularly, to methods and apparatus for providing complete routing coverage utilizing reduced switch matrices.
2. History Of The Prior Art
Switch matrices allow combinations of signals appearing on a large number of input signal conductors to be provided at a more limited number of output conductors. Essentially, a switch matrix comprises a first set of input conductors and a second set of output conductors. The input conductors may be selectively joined to the set of output conductors by switching devices. In this manner, selective combinations of a typically large number of input signals may be furnished to a smaller number of output conductors. In a full (or one hundred percent) connection matrix all of the of the input conductors may be selectively joined to each of the output conductors. Such an arrangement may be pictured as rows and columns of intersecting conductors with a switch which may be closed at each intersection.
Switch matrices are used for many purposes in computer and other digital systems. For example, switch matrices are an essential part of field programmable logic arrays. Field programmable logic arrays may be used in digital systems to provide particular logic operations using binary input signals. A programmable logic array includes a switch matrix the output conductors of which are connected to gates which allow a plurality of input values to be manipulated in accordance with various Boolean functions. By connecting the input conductors to various AND gates and the outputs of the AND gates (product terms) to various OR gates, a particular Boolean function which is the sum of the product terms produced by the AND gates may be furnished at the output of any OR gate. The Boolean output function provided at the output of each of the OR gates is programmable by a user by programming the connections to be made by the switching devices between the input conductors and the output conductors of the switch matrix using devices such as electrically programmable read only memory (EPROM) cells, fuses, or flash erasable electrically programmable read only memory (EEPROM) cells. Normally, a switch matrix is manufactured with the switching devices in place; and a user programs the switching devices necessary to provide the connections for the logic functions the user desires.
A full connection switch matrix includes physical switching devices which allow all of the input conductors to connect to all of the output conductors. The provision of switching devices at each intersection between input and output conductors requires a large amount of die area. In a full connection matrix where each input conductor may be connected to each output conductor, the switching devices may occupy one-quarter of the entire die area. Consequently, field programmable switch matrices often use less than a switching device at each intersection in order to reduce the die area used and to increase the speed of operation by reducing the length of the various conductors within the matrix. One arrangement for providing a reduced switch matrix has been able to achieve full coverage of all combinations of input conductors to output conductors by assigning switches to connect input and output conductors on a incrementing serial basis which shifts each time all of the input conductors have been assigned connections to output conductors. Thus, in a matrix of eight input conductors and four output conductors, the input conductors are serially assigned switches allowing connection to each of the output conductors (also on a serial basis) in the following pattern where each two digits indicate first the input conductor and second the output conductor to which it may be connected (11, 22, 33, 44, 51, 62, 73, 84). When all of the input conductors have been assigned, the pattern is repeated but the connections are shifted by some amount (e.g., 12, 23, 34, 41, 52, 63, 74, 81). The pattern continues to be repeated, shifting each sequence by the same number, until a predetermined number of sequences of input conductors have been assigned. This method of assigning switches to connect input and output conductors has been able to achieve full coverage of input combinations with a reduction in the number of switches to approximately sixty percent of the number required in a full connection matrix.
There are a class of field programmable gate arrays in which, rather than a single switch matrix, a plurality of small switching matrices are utilized in order to provide the output signals which are sent to the AND and OR gates to provide the logical output signals. In these gate arrays, in order to keep the size of the switch matrices to a minimum, individual matrices designed in the manner described above have been reduced to one-half the number of switches of a full connection matrix. To realize this number of switches in the switch matrices designed with a serial pattern of connections which shifts with each cycle of input conductors, those switches of the reduced matrix greater than is necessary to provide full coverage have simply been eliminated by truncating the arrangement so that only a number of sequences of switches equal to one-half of the switches of a full connection matrix are used. These physical switches are arranged so that they require only one-half the die area required by a full connection matrix and provide almost all of the output combinations available in a full connection matrix. A small matrix of this sort is duplicated the number of times required for the particular gate array and each matrix is associated with an individual set of AND and OR gates placed at each of the physical positions convenient to the layout to provide the complete gate array.
Unfortunately, such a reduced matrix does not provide full coverage of all of the possible combinations of input conductors. It is often desirable to assure a user that full coverage is provided. Without that assurance, it is very difficult to ascertain that coverage for desired combinations exist without actually utilizing the gate array, and determining whether it fails or not. Moreover, gate arrays are often reprogrammed to provide new logic functions after some initial period of use. This may occur, for example, when other portions of circuitry with which the gate array is used are updated or added to. Thus a determination initially made that coverage is sufficient may be invalid at some later date.
Recently another arrangement has been devised which reduces the number of switches utilized in a switching matrix by an even greater amount to a fraction of the number used in a full switch matrix. This switch matrix arrangement includes a number of input conductors and a number of output conductors intersecting in row and column fashion, and having switching devices placed on a random basis in each row joining selected ones of the input conductors to selected ones of the output conductors at the logical intersections to make connections between input and output conductors. In one embodiment, the fraction of switching devices in each row and each column is equal to the fraction of the total number of switching devices divided by the total number of intersections in the matrix. It has been found that such a switching matrix when carefully selected provides almost all possible combinations of connections between the input and the output conductors even though the number of switching devices is reduced to one-half of the number used in a full connection switching matrix. Since these matrices typically use one-half the number of switching devices used in a full connection matrix, a plurality of identical random switch matrices may be conveniently used in place of the shifting sequence arrangements described above to provide field programmable gate arrays.
However, some combinations of input signals are simply not available in either form of reduced switching matrix where the number of switches is reduced to one-half. It is desirable to guarantee to a user of a field programmable gate array or other device using these reduced size matrices that all possible combinations of input conductors are available while still utilizing reduced switch matrices designed in the manner described above.